import entity.TreeNode;

public class SearchInBinarySearchTree {
    /*
    * 700. 二叉搜索树中的搜索
    * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
    * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。
    * 如果节点不存在，则返回 null 。
    *
    * 数中节点数在 [1, 5000] 范围内
    * 1 <= Node.val <= 10^7
    * root 是二叉搜索树
    * 1 <= val <= 10^7
    * */
    public static void main(String[] args){

    }

    // 我的想法：递归啊
    public TreeNode searchBST(TreeNode root, int val){
        if(root == null)
            return null;
        if(root.val == val)
            return root;
        if(root.val < val)
            return searchBST(root.right, val);
        if(root.val > val)
            return searchBST(root.left, val);
        return null;
    }

    // 迭代也是可以的
    public TreeNode searchBST2(TreeNode root, int val){
        if(root == null || root.val == val)
            return root;
        while (root != null){
            if(root.val > val) root = root.left;
            else if(root.val < val) root = root.right;
            else return root;
        }
        return null;
    }
}
